Error-correcting codes are used in a variety of systems such as communication and data storage systems to achieve high data reliability. A typical error correction coding code consists of an encoder and decoder.
FIG. 1 shows a prior art system 100 with conventional data input/output (I/O) and generic encoder 102. As illustrated, generic encoder 102 typically accepts as an input a set of data symbols, U 104, consisting of Z symbols, where the Z=K+T symbols are the sum of K information symbols (i.e., raw symbols that need to be transmitted) and possible T overhead symbols (i.e., extra symbols for error detection and/or trellis termination for convolutional and turbo codes). Some encoders 102 such as convolutional encoder do not require the data symbols to be of fixed length; the data symbols can be theoretically of infinite length. Encoder 102 maps the input U 104 according to well-defined rules to a codeword C 106 of length N data symbols. The ratio Q=K/N is the code rate. If higher code rates are needed, puncturing can be used to delete some of the N data symbols in C 106. If the code is systematic, then C 106 will include the entire set of data symbols, U, as well as a set of redundant parity symbols, P. If the code is non-systematic, then C 106 will contain only a set of parity symbols, P. It is also possible to have partially systematic codes, either by design, or for example when puncturing is used to delete some of the data and parity symbols in a systematic code to obtain a higher code rate. In this case, the punctured codeword 106 will contain a subset of U and a subset of P.
FIG. 2 shows a conventional decoding system 200 with a soft-in soft-out (SISO) decoder 202. The SISO decoder typically operates on a set of received hard or soft values, V 204 that have a correspondence to the symbols in a transmitted codeword, C 106 (FIG. 1). It also accepts a separate set of soft a priori information values, A 206, that have a correspondence to some or all of the data symbols in U 104 and/or P (e.g., in a codeword 106). On the other hand, the SISO decoder 202 outputs a set of hard decisions, D 208. The decisions in D usually correspond either to hard estimates of the data symbols in U or to hard estimates of the symbols in the entire codeword, C. Decoder 202 also outputs soft reliability values, R 210, corresponding to some or all of the hard decisions in D. The values in inputs V and A are often expressed in log-likelihood-ratio (LLR) format and, if independent or assumed to be independent, can simply be viewed as additive information.
Examples of powerful error-correcting codes are turbo codes, turbo product codes, and low-density parity-check (LDPC) codes. For explanation and comparison purposes, parallel turbo codes are used as representative error-correcting codes. FIG. 3 shows a common parallel turbo-code encoder 300 consisting of two recursive systematic convolutional (RSC) encoders 302 and 304 in parallel, an interleaver 306 to scramble data symbols, and a puncturing unit 308 to achieve higher code rates. The data symbols 104 are fed to RSC1 encoder 302 to generate the first set of parity symbols. An interleaved version of the data symbols 104 is fed to RSC2 encoder 304 to generate the second set of parity symbols. All three sets, namely, the data symbols, the first set of parity symbols, and the second set of parity symbols are passed to the puncturing unit 308 to produce the systematic (or partially systematic) part, S 310, the first parity part, P1 312, and the second parity part, P2 314, respectively.
The turbo decoding process is usually performed in an iterative manner by exchanging soft decoding information (i.e., extrinsic information) between the constituent soft-in soft-out (SISO) decoders. This way, each constituent decoder takes advantage of the extrinsic information produced by the other decoder at the previous step. The core of each constituent decoder is based on a SISO algorithm such the one depicted in FIG. 2. In classical systematic turbo decoder, for example, the values in V 204 provide information about the symbols in both U 104 and parity parts (P1 312 or P2 314), and the values in A 206 provide additional a priori information about the data symbols in U 104, but not necessarily about the parity symbols (P1 312 or P2 314). Note that the reliability values at the output of the decoder are useful when the given decoder is part of a concatenated or iterative decoding scheme. This is the case for turbo and turbo-like decoders where the a priori information used by one constituent decoder is derived from the reliability values produced by one or more other constituent decoder(s). Examples of soft output decoding algorithms include the log a posteriori probability (log-APP) and max-log-APP algorithms.